package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/nim-game/description/'>Nim 游戏(Nim Game)</a>
 * <p>
 * 你和你的朋友，两个人一起玩 Nim 游戏：
 *     <ul>
 *         <li>桌子上有一堆石头。</li>
 *         <li>你们轮流进行自己的回合， 你作为先手 。</li>
 *         <li>每一回合，轮到的人拿掉 1 - 3 块石头。</li>
 *         <li>拿掉最后一块石头的人就是获胜者。</li>
 *     </ul>
 *     假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
 * </p>
 *
 * <p>
 *     <b>示例：</b>
 *     <pre>
 * 示例 1：
 *      输入：n = 4
 *      输出：false
 *      解释：以下是可能的结果:
 *          1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
 *          2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
 *          3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
 *          在所有结果中，你的朋友是赢家。
 *
 * 示例 2：
 *      输入：n = 1
 *      输出：true
 *
 * 示例 3：
 *      输入：n = 2
 *      输出：true
 *     </pre>
 * </p>
 *
 * <p>
 *     <b>提示：</b>
 *     <ul>
 *         <li>1 <= n <= 2^31 - 1</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/30 11:53
 */
public class LC0292NimGame_S {
    static class Solution {
        public boolean canWinNim(int n) {
            /*
            如果落到先手的局面为「石子数量为 1-3」的话，那么先手必胜；
            如果落到先手的局面为「石子数量为 4」的话，那么先手决策完（无论何种决策），交到后手的局面为「石子数量为1-3」，即此时后手必胜，对应先手必败
                （到这里我们有一个推论：如果交给先手的局面为 4 的话，那么先手必败）；
            如果落到先手的局面为「石子数量为 5-7」的话，那么先手可以通过控制选择石子的数量，来使得后手处于「石子数量为4」的局面（此时后手必败），因此先手必胜；
            如果落到先手的局面为「石子数量为8」的话，由于每次只能选1-3个石子，因此交由后手的局面为5-7，根据流程3 我们知道此时先手必败； ...

            到这里，我们猜想 当起始局面石子数量为4的倍数，则先手必败，否则先手必胜（即 n % 4 != 0 时，先手必胜）。
             */
            return n % 4 != 0;
        }


    }


}
